#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

char* main_str;
int len_main_str;
int max_deg;
int len;
typedef struct
    {
        int *adj;
        int index;
        int deg;
    }node;
node *n1;
int numb_node;
int num_comb;

int combination(char* str,int start,int index)
    {
        int temp;
        char temp_str[100];
        if(strlen(str)==len)
            {
            check_dominate(str);
            return index;
            }

        strcpy(temp_str,str);
        temp=start;
        start=strlen(str);
        while(temp<len_main_str)
            {
                temp_str[start]=main_str[++temp];
                temp_str[start+1]='\0';
                index=combination(temp_str,temp,index);
            }
            return index;
    }

int* input()
    {
        int *sorted_node;
        int deg=0;
        int inp;
        n1=(node*)malloc(numb_node*sizeof(node));
        sorted_node=(int*)malloc(numb_node*sizeof(int));
        int i,j;
        for(i=0;i<numb_node;i++)
            {
                n1[i].adj=(int*)malloc(numb_node*sizeof(int));
                printf("Enter the row of adjacency matrix for graphnode %d\n",i+1);
                for(j=0;j<numb_node;j++)
                    {
                        scanf("%d",&inp);
                        n1[i].adj[j]=inp;
                        if(inp)
                            deg=deg+1;;
                    }
                if(max_deg<deg)
                    max_deg=deg;
                n1[i].deg=deg;
                deg=0;
                n1[i].index=i;
                sorted_node[i]=i;
            }
        return sorted_node;
    }

int check_dominate(char *test)
    {
    	int q,p;
		int sum;
		int temp;
		for(p=0;p<numb_node;p++)
			{
				sum=0;
				for(q=0;q<len;q++)
					{
						temp=test[q]-48;
						sum=sum+n1[temp].adj[p];
						if(temp==p)
								sum++;
					}
				if(sum==0)
						return;
			}

		printf("the minimum dominating set is\n");
		for(p=0;p<len;p++)
				printf("%d\t",test[p]-47);
		exit(0);
	}

void quicksort(int *sort,int p,int r)
    {
        int q;
        if(p<r)
            {
                q=partition(sort,p,r);
                quicksort(sort,p,q-1);
                quicksort(sort,q+1,p);
            }
    }

int partition(int *a,int p,int r)
    {
        int x=n1[a[r]].deg;
        int i=p-1;
        int j;
        int temp;
        for(j=p;j<r;j++)
            {
                if(n1[a[j]].deg<=x)
                    {
                        i=i+1;
                        temp=a[i];
                        a[i]=a[j];
                        a[j]=temp;

                    }
            }
        temp=a[i+1];
        a[i+1]=a[r];
        a[r]=temp;
        return (i+1);
    }

int main()
    {
        int x=0,c;
        int counter=0;
        int *sort;
        char b[2];
        printf("Enter the number of nodes in graph\n");
        scanf("%d",&numb_node);
        sort=input();
        main_str=(char*)malloc((numb_node+1)*sizeof(char));
        quicksort(sort,0,numb_node-1);
        len=numb_node/(max_deg+1);

        if(numb_node%(max_deg+1)>0)
            len++;
        x=0;

        while(x<numb_node)
                {
                    main_str[numb_node-x-1]=sort[x]+48;
                    x++;
                }
        main_str[x]='\0';
        len_main_str=x;
        x=0;
        while(len<len_main_str)
        	{
                while(x<len_main_str)
                    {
                        b[0]=main_str[x];
                        b[1]='\0';
                        c=combination(b,x,0);
                        x++;
                        num_comb=0;
                        counter=0;
                   }
                x=0;
                len++;
            }
        }
